package datastructure.day03;

import java.util.Arrays;
import java.util.Iterator;


/**
 * @author: Gan
 * @date 2021/4/30 0030 19:46
 * @description: 用数组实现线性表(参考数组实现栈和队列)
 **/
public class MyListBasedArray<T> extends ListBasedArray implements Iterable<T> {

    private int length;
    private T[] arr;

    public MyListBasedArray() {
        this.arr = (T[]) new Object[16];
    }

    public boolean isEmpty() {
        return length == 0;
    }

    //查找元素
    @Override
    public boolean contains(String value) {
        for (Object obj : arr) {
            if (obj == value) {
                return true;
            }
        }
        return false;
    }

    //删除元素
    @Override
    public void remove(int index) {
        if (isEmpty())
            throw new RuntimeException("Array is empty!");
        //参数验证
        if (index < 0 || index > length - 1) {
            throw new RuntimeException("Illegal parameter!");
        }
        //删去元素
        if (length - index >= 0)
            System.arraycopy(arr, index + 1, arr, index, length - index);
        length--;
    }

    //添加元素
    @Override
    public boolean addValue(int index, String value) {
        //数组满了
        if (length == arr.length) {
            int newLen = getLength();
            grow(newLen);
        }
        //参数验证
        if (index < 0 || index > length)
            return false;
        //将元素插入
        for (int i = length; i > 0; i--) {
            if (i >= index) {
                arr[i] = arr[i - 1];
            }
        }
        arr[index] = (T) value;
        length++;
        return true;
    }

    //扩容
    private void grow(int newLen) {
        Object[] newArr = new Object[newLen];
        if (length >= 0)
            System.arraycopy(arr, 0, newArr, 0, length);
        arr = (T[]) newArr;
    }

    //得到长度
    private int getLength() {
        int oldLen = length;
        int newLen = oldLen << 1;
        // 判断新长度是否溢出
        if (newLen <= 0 || newLen > Integer.MAX_VALUE - 8) {
            throw new RuntimeException("can not add!");
        }
        return newLen;

    }

    //修改元素
    @Override
    public boolean setValue(String oldValue, String newValue) {
        for (int i = 0; i < length; i++) {
            if (oldValue.equals(arr[i])) {
                arr[i] = (T) newValue;
                return true;
            }
        }
        return false;
    }


    @Override
    public String toString() {
        return "MyListBasedArray{" +
                "length=" + length +
                ", arr=" + Arrays.toString(arr) +
                '}';
    }


    @Override
    public Iterator<T> iterator() {
        return new MyListIterator();
    }

    private class MyListIterator implements Iterator<T> {
        private int current = 0;

        @Override
        public boolean hasNext() {
            return current < length;
        }

        @Override
        public T next() {
            T value = arr[current++];
            return value;
        }
    }
}
